package leetcode每日一题.leetcode20213;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 *
 * 2. 算法分析
 *      题目很简单，暴力做就可以，但是效率不高，时间复杂度为O(nums * bit(num)) ，思考能否将时间复杂度控制到线性时间之内
 *      
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q003_比特位计数 {

    /**
     * 按照题目要求暴力求解即可
     * @param num
     * @return
     */
    public static int[] countBits1(int num) {
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        for(int i = 1; i <= num; i++) { // 扫描每个数
            // 计算出i的二进制中有多少个1
            int ones = 0;
            int cur = i;
            while(cur > 1) {
                ones = (cur % 2 == 1) ? ones + 1 : ones;
                cur /= 2;
            }
            // 由于条件为cur > 1,所以退出循环的时候cur可能为1或者0，我们需要判断一下cur当前状态
            // 如果cur当前为1，ones需要+1
            if (cur == 1) {
                ones++;
            }
            temp.add(ones);
        }
        int[] res = new int[temp.size()];
        for(int i = 0; i < temp.size(); i++) {
            res[i] = temp.get(i);
        }
        return res;
    }

    /**
     * 优化上述实现
     * 分析i与i+1之间的二进制有什么联系?
     *         0       1       2       3      4       5       6       7        8        9       10       11       12
     *      0000    0001    0010    0011   0100    0101    0110    0111     1000     1001     1010     1011     1100
     * 动态规划+位运算实现，下面的主要想法是这样的：
     *      假设当前元素为x，如果存在这样的y，y与x之间的二进制的1的个数只相差1，则bits[x] = bits[y] + 1  0 <= y < x
     *      问题是这样的y是否对于每个x都存在吗?如果存在如何求出来呢?
     *      1. 存在性问题的解决?
     *          存在性是比较好看出来的，因为假设当前32位二进制数中不可能全部是1，因为此时就会超出整形的范围 int类型的范围
     *          [-2^32-1,2^32-1]之间，所以只需要将x其中一个1变为0就可以实现
     *
     *      2. 具体如何找到这样的y?
     *          对于中间位置的元素实际上我们并不好操作，但是对于一个二进制的最高位我们比较好求主要到，我们就维护二进制的最高位1
     *          如果一个10进制数为2的幂，则这个数的二进制中只有最高位为1，其余全部为0，假设这个数为z，则x-z就是我们要找的数y。
     *          由于n与n-1之间存在这样的关系：n的最低位1恰好对应于n-1的1，所以由于z为2的幂，最低位和最高位1相同，所以z与z-1
     *          的与运算 恰好为0，通过此我们 就可以找到z（z就是我们维护的最高位1的二进制），此时bit[x] = bit[x - z] + 1
     *          这就是此道问题的动态转移方
     * @param num
     * @return
     */
    public static int[] countBits2(int num) {
        int[] bits = new int[num+1];
        int heigthbit = 0;
        for(int i = 1; i <= num; i++) {
            if((i & (i-1)) == 0) {
                heigthbit = i;
            }
            bits[i] = bits[i - heigthbit] + 1;
        }
        return bits;
    }

    /**
     * 通过上述的分析，维护最高位1的启发，我们知道，我们还可以维护最低位1，大致想法一致，问题就是如何寻找这个最低位1?
     * 对于一个二进制数，其最低位的元素决定了当前这个数是奇数还是偶数，如果最低位为0，则为偶数，为1则为奇数。所以此处
     * 很可能会分奇数偶数来讨论，我们先看偶数的情况，假设当前的x为偶数bits[x] = bits[x >> 1]，这个式子之所以成立的
     * 原因：去掉x的最低位1相当于对x做了一次左移运算，而且由于当前x为偶数，最低位为0，所以此时左移并不会影响1的个数
     * 由此我们知道如果x为奇数，最低位为1，左移会造成最低位1的缺失(会自动补0)，所以bits[x] = bits[x>>1] + 1
     * 综上 bits[x] = bits[x >> 1] + (x % 2)
     * @param num
     * @return
     */
    public static int[] countBits3(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }


    /**
     * dp 设置最低位
     * 上述我们反复利用到n与n-1之间的与运算性质，这里也是一样，由于n和n-1之间的关系：n的最低位1恰好对应n-1的0
     * 所以做一次n & n - 1恰好可以将n的最低位1变为0，而其余不变，这样n的二进制中就少了一个1，从而可以得到下面
     * 的关系：bits[n] = bits[n & n-1] + 1;
     * @param num
     * @return
     */
    public static int[] countBits4(int num) {
        int[] bits = new int[num+1];
        for(int i = 1; i <= num; i++) {
            bits[i] = bits[i & (i-1)] + 1;
        }
        return bits;
    }
}
